Non-small cell lung cancer (NSCLC) constitutes the principal cause of cancer death for both men and women in North America. Despite vigorous efforts at curbing tobacco consumption, the incidence of lung cancer has yet to show a substantial overall decline and in fact is increasing in some groups, particularly women. As a result, novel therapeutic strategies aimed at improving survival and cure rates are needed. This is a multicenter, nonblinded randomized cooperative group trial to compare whether 2 drugs cisplatin and vinorelbine given adjuvantly will significantly impact disease-free survival and overall survival. Patients eligible for this study must have histological evidence of a non-small cell primary cancer of the lung that has been completely resected and fulfills the required staging criteria.